1. Field of the Invention
The present invention relates to a file system incorporating a non-volatile semiconductor memory device such as a flash memory, and a method for managing such a file system.
2. Description of the Related Art
In recent years, much attention has been paid to techniques for employing a non-volatile semiconductor memory device which is capable of electrically writing and erasing data therein (e.g., a flash memory) as an alternative drive for hard disk drives, which are capable of magnetically writing and erasing data therein.
Flash memories permit data reading at a rate which is about ten thousand times faster than that of hard disk drives, and data writing at a rate which is about one thousand times faster than that of hard disk drives. Other advantages of flash memories include their adaptability to be constructed in small size and with small weight, excellent shock resistance, and excellent portability. Flash memories are especially suitable for storing and reading small amounts of data at a fast rate.
However, flash memories have the following problems. Before writing new data in a storage region of a flash memory in which data is already written, it is necessary to erase existing data. A relatively long data erase time on the order of several dozen milliseconds to several seconds is required because data are deleted in units of several Kbytes. Moreover, flash memories can only guarantee that data can be safely written or erased up to a finite number of times.
In view of the aforementioned disadvantages of flash memories, in order to employ a flash memory as an alternative hard disk drive, it is necessary to provide a file system which is tailored to flash memories, i.e., a file system in which data are processed by units of several hundred bytes (as in hard disk drives) and in which data management is efficiently performed while minimizing data erasure. Such a file system is disclosed in Japanese Laid-Open Publication No. 6-95955, for example.
U.S. Pat. No. 5,544,119 discloses a processing method to be performed at the time when the power supply is restored after an interruption. U.S. Pat. No. 5,544,356 discloses a method for reconstructing a file system.
However, the aforementioned publications do not address situations where a flash memory or a file system for performing various processes may be used with a relatively unstable supply of power, e.g., in the case of using a battery as the power supply means. Hence, any unexpected interruption of the power supply, i.e., if the power supply is interrupted even for a short moment (e.g., due to exhaustion of the battery) during the operation of a flash memory or file system, may make it impossible to properly read the data stored in the flash memory.
The aforementioned problem will be more specifically described. Firstly, the current states of storage regions in which data can be stored (hereinafter referred to as xe2x80x9csectorsxe2x80x9d) are indicated by sector state information, which represents one of the three states xe2x80x9cUNUSEDxe2x80x9d xe2x80x9cIN USExe2x80x9d, or xe2x80x9cINVALIDxe2x80x9d. Therefore, if an interruption of the power supply occurs during update of the data stored in a given sector, the data may incorrectly be recognized as being valid (i.e., not corrupt) even though the data has not been properly updated, based on the sector state information. This process of sector data update will be described with reference to a flowchart shown in FIG. 10.
According to the flowchart shown in FIG. 10, the sector state information of a sector which stores existing data (supposing that this data is to be updated) is changed from xe2x80x9cIN USExe2x80x9d to xe2x80x9cINVALIDxe2x80x9d (Step 101). Then, the sector state information of another sector is changed from xe2x80x9cUNUSEDxe2x80x9d to xe2x80x9cIN USExe2x80x9d (Step 102). Thereafter, the update data is written to the sectors whose sector state information has been changed to xe2x80x9cIN USExe2x80x9d (Step 103). Steps 101 to 103 are repeated until there is no more data to be written.
If the power supply is interrupted immediately after Step 102 or during Step 103, so that the writing of data to the flash memory is suddenly terminated, the sector state information of this sector remains to be xe2x80x9cIN USExe2x80x9d although the writing of update data to this sector was not properly completed. Therefore, when the power supply is restored, the file system will incorrectly recognize the data stored in this sector as valid.
Secondly, if an interruption of the power supply occurs in the case where all of the data in one block of sectors (hereinafter referred to as a xe2x80x9ctarget blockxe2x80x9d) is to be erased and thereafter the file system is reconstructed, it is possible that the same data may be left stored in two blocks, or all of the data in the one block may not have been completely erased. This file system reconstruction process will be described with reference to a flowchart shown in FIG. 11.
According to the flowchart shown in FIG. 11, a block is previously secured or reserved as a reserve block, all of whose sectors have had their data erased so that the sector state information of all the sectors in that block indicates xe2x80x9cUNUSEDxe2x80x9d. Then, any data within the target block that should be preserved is copied to the reserve block (Step 111). That is, any data except for the data stored in the sectors whose sector state information indicates xe2x80x9cINVALIDxe2x80x9d and the sector state information associated with such sectors must be copied to the reserve block. Furthermore, a block number of the target block, which is included in the location information other than the sectors whose sector state information indicates xe2x80x9cINVALIDxe2x80x9d, overwrites the block number of the reserve block (Step 112). Finally, the data in the target block (whose data was copied to the reserve block at Step 111) is erased, and this block is secured as a reserve block for use in a subsequent file system reconstruction (Step 113).
If the power supply is interrupted before the execution of Step 113 or during Step 113, it is possible that the same data may be left stored in two blocks, or all of the data in one block may not have been completely erased, when the power supply is restored. As a result, it is impossible to secure a new reserve block.
According to the present invention, there is provided a file system including at least one non-volatile semiconductor memory device, the at least one non-volatile semiconductor memory device including a plurality of erasure blocks, each erasure block including a plurality of sectors, wherein the file system includes: a file system memory section for storing block state information for each erasure block, the block state information representing one of a plurality of block states, and for storing sector state information for each sector, the sector state information representing one of a plurality of sector states: and a file system control section for, when accessing the at least one non-volatile semiconductor memory device, guaranteeing integrity of data already stored in the at least one non-volatile semiconductor memory device based on the block state information and on the sector state information in the file system memory section.
In one embodiment of the invention, the file system memory section is provided on a RAM having substantially no constraints concerning data updates, and the file system control section refers to the block state information and the sector state information stored in the RAM when accessing the at least one non-volatile semiconductor memory device.
In another embodiment of the invention, the plurality of block states represented by the block state information include the five states of xe2x80x9cUNUSEDxe2x80x9d, xe2x80x9cINCLUDES DATAxe2x80x9d, xe2x80x9cBLOCK FULLxe2x80x9d, xe2x80x9cRECEIVING DATAxe2x80x9d, and xe2x80x9cERASING ORIGINAL BLOCKxe2x80x9d, and the file system control section includes: means for changing the block state information of a first erasure block from xe2x80x9cUNUSEDxe2x80x9d to xe2x80x9cRECEIVING DATAxe2x80x9d, the first erasure block being previously reserved as a reserve erasure block for use in a file system reconstruction process; means for transferring data stored in a second erasure block to the first erasure block and storing the transferred data in the first erasure block; means for, after completing the transfer and storage of the data, changing the block state information of the first erasure block from xe2x80x9cRECEIVING DATAxe2x80x9d to xe2x80x9cERASING ORIGINAL BLOCKxe2x80x9d, erasing the data in the second erasure block, reserving the second erasure block as a new reserve erasure block, and changing the block state information of the second erasure block from xe2x80x9cINCLUDES DATAxe2x80x9d or xe2x80x9cBLOCK FULLxe2x80x9d to xe2x80x9cUNUSEDxe2x80x9d; and means for changing the block state information of the first erasure block from xe2x80x9cERASING ORIGINAL BLOCKxe2x80x9d to xe2x80x9cINCLUDES DATAxe2x80x9d.
In still another embodiment of the invention, the at least one non-volatile semiconductor memory device includes a plurality of erasure blocks of different block sizes, and at least one erasure block is previously reserved as a reserve erasure block for the erasure blocks of each block size within each non-volatile semiconductor memory device, the reserve erasure block being for use in the file system reconstruction process.
In still another embodiment of the invention, the file system includes a plurality of non-volatile semiconductor memory devices, wherein each non-volatile semiconductor memory device includes a plurality of erasure blocks of different block sizes, and wherein at least one erasure block is previously reserved as a reserve erasure block for the erasure blocks of each block size throughout the plurality of non-volatile semiconductor memory devices, the reserve erasure block being for use in the file system reconstruction process.
In still another embodiment of the invention, the at least one erasure block previously reserved as a reserve erasure block for use in the file system reconstruction process is equal to or larger in size than any other erasure block.
In still another embodiment of the invention, the at least one erasure block previously reserved as a reserve erasure block for use in the file system reconstruction process is equal to or larger in size than any other erasure block.
Alternatively, there is provided a file system including at least one non-volatile semiconductor memory device, the at least one non-volatile semiconductor memory device including a plurality of sectors, wherein the file system includes: a file system memory section for storing sector state information for each sector, the sector state information representing one of a plurality of sector states; a file system control section for, when accessing the at least one non-volatile semiconductor memory device, guaranteeing integrity of data already stored in the at least one non-volatile semiconductor memory device based on the sector state information in the file system memory section, wherein the plurality of sector states represented by the sector state information include the five states of xe2x80x9cUNUSEDxe2x80x9d, xe2x80x9cWRITING DATAxe2x80x9d, xe2x80x9cDATA WRITE COMPLETExe2x80x9d, xe2x80x9cDATA VALIDxe2x80x9d, and xe2x80x9cDATA INVALIDxe2x80x9d, and wherein the file system control section includes: means for changing the sector state information of a first sector in which data is written fromxe2x80x9cUNUSEDxe2x80x9d to xe2x80x9cWRITING DATAxe2x80x9d; means for changing the sector state information of the first sector from xe2x80x9cWRITING DATAxe2x80x9d to xe2x80x9cDATA WRITE COMPLETExe2x80x9d after the data writing for the first sector is completed; and means for a) when the data written to the first sector is new data, changing the sector state information of the first sector from xe2x80x9cDATA WRITE COMPLETExe2x80x9d to xe2x80x9cDATA VALIDxe2x80x9d, or b)when the data written to the sector is update data of existing data, changing the sector state information of a second sector from xe2x80x9cDATA VALIDxe2x80x9d to xe2x80x9cDATA INVALIDxe2x80x9d, and thereafter changing the sector state information of the first sector from xe2x80x9cDATA WRITE COMPLETExe2x80x9d to xe2x80x9cDATA VALIDxe2x80x9d.
In one embodiment of the invention, the file system control section includes: means for, during initialization of the file system performed when the power supply is restored, searching among the plurality of erasure blocks for an erasure block having the xe2x80x9cERASING ORIGINAL BLOCKxe2x80x9d block state information, and if an erasure block having the xe2x80x9cERASING ORIGINAL BLOCKxe2x80x9d block state information exists, locating a further erasure block which has the same logic block number as a logic block number of the erasure block having the xe2x80x9cERASING ORIGINAL BLOCKxe2x80x9d block state information and which has the xe2x80x9cINCLUDES DATAxe2x80x9d or xe2x80x9cBLOCK FULLxe2x80x9d block state information based on the block state information in the file system memory section, means for erasing data in the further erasure block, and after completing the erasure, changing the block state information of the further erasure block from xe2x80x9cINCLUDES DATAxe2x80x9d or xe2x80x9cBLOCK FULLxe2x80x9d to xe2x80x9cUNUSEDxe2x80x9d, and means for changing the state information of the erasure block having the xe2x80x9cERASING ORIGINAL BLOCKxe2x80x9d block state information from xe2x80x9cERASING ORIGINAL BLOCKxe2x80x9d to xe2x80x9cINCLUDES DATAxe2x80x9d.
In another embodiment of the invention, the plurality of block states represented by the block state information include the five states of xe2x80x9cUNUSEDxe2x80x9d, xe2x80x9cINCLUDES DATAxe2x80x9d, xe2x80x9cRECEIVING DATAxe2x80x9d, xe2x80x9cERASING ORIGINAL BLOCKxe2x80x9d, and xe2x80x9cFORMATTING ORIGINAL BLOCKxe2x80x9d, and wherein the file system control section includes: means for changing the block state information of a first erasure block from xe2x80x9cUNUSEDxe2x80x9d to xe2x80x9cRECEIVING DATAxe2x80x9d, the first erasure block being previously reserved as a reserve erasure block for use in a file system reconstruction process; means for transferring data stored in a second erasure block to the first erasure block and storing the transferred data in the first erasure block; means for, after completing the transfer and storage of the data, changing the block state information of the first erasure block from xe2x80x9cRECEIVING DATAxe2x80x9d to xe2x80x9cERASING ORIGINAL BLOCKxe2x80x9d, erasing the data in the second erasure block, reserving the second erasure block as a new reserve erasure block after completing the erasure, and changing the block state information of the second erasure block from xe2x80x9cINCLUDES DATAxe2x80x9d to xe2x80x9cUNUSEDxe2x80x9d;
means for changing the block state information of the first erasure block from xe2x80x9cERASING ORIGINAL BLOCKxe2x80x9d to xe2x80x9cFORMATTING ORIGINAL BLOCKxe2x80x9d, and formatting, the second erasure block; and means for changing the block state information of the first erasure block from xe2x80x9cFORMATTING ORIGINAL BLOCKxe2x80x9d to xe2x80x9cINCLUDES DATAxe2x80x9d after completing the formatting.
In still another embodiment of the invention, each erasure block stores therein an allowable number of erasures to be performed for the erasure block, and the file system control section includes: means for, during the formatting, storing in the second erasure block a number obtained by subtracting one from the allowable number of erasures previously stored in the second erasure block; and means for, during the file system reconstruction process, selecting as the first erasure block an erasure block having a largest allowable number of erasures among all of the plurality of erasure blocks except for the reserve erasure block.
In still another embodiment of the invention, each erasure block is banned from use when the allowable number of erasures of the erasure block equals zero or less.
In still another embodiment of the invention, each erasure block stores therein a number of erasures having been performed for the erasure block, and the file system control section includes: means for, during the formatting, storing in the second erasure block a number obtained by adding one to the number of erasures previously stored in the second erasure block; and means for, during the file system reconstruction process, selecting as the first erasure block an erasure block having a smallest number of erasures among all of the plurality of erasure blocks except for the reserve erasure block.
In still another embodiment of the invention, each erasure block is banned from use when the number of erasures having been performed for the erasure block has exceeded a largest value permitted by specifications of the at least one non-volatile semiconductor memory device.
In still another embodiment of the invention, the at least one non-volatile semiconductor memory device includes a plurality of erasure blocks of different block sizes, and at least one erasure block is previously reserved as a reserve erasure block for the erasure blocks of each block size within each non-volatile semiconductor memory device, the reserve erasure block being for use in the file system reconstruction process.
In still another embodiment of the invention, the file system includes a plurality of non-volatile semiconductor memory devices, wherein each non-volatile semiconductor memory device includes a plurality of erasure blocks of different block sizes, and wherein at least one erasure block is previously reserved as a reserve erasure block for the erasure blocks of each block size throughout the plurality of non-volatile semiconductor memory devices, the reserve erasure block being for use in the file system reconstruction process.
In still another embodiment of the invention, the at least one erasure block previously reserved as a reserve erasure block for use in the file system reconstruction process is equal to or larger in size than any other erasure block.
In still another embodiment of the invention, the at least one erasure block previously reserved as a reserve erasure block for use in the file system reconstruction process is equal to or larger in size than any other erasure block.
Alternatively, there is provided a file system including at least one non-volatile semiconductor memory device, the at least one non-volatile semiconductor memory device including a plurality of sectors, wherein the file system includes: a file system memory section for storing sector state information for each sector, the sector state information representing one of a plurality of sector states; a file system control section, for, when accessing the at least one non-volatile semiconductor memory device, guaranteeing integrity of data already stored in the at least one non-volatile semiconductor memory device based on the sector state information in the file system memory section, wherein the plurality of sector states represented by the sector state information include the five states of xe2x80x9cUNUSEDxe2x80x9d, xe2x80x9cWRITING DATAxe2x80x9d, xe2x80x9cDATA WRITE COMPLETExe2x80x9d, xe2x80x9cDATA VALIDxe2x80x9d, and xe2x80x9cDATA INVALIDxe2x80x9d, and wherein the file system control section includes: means for changing the sector state information of a first sector in which data is written from xe2x80x9cUNUSEDxe2x80x9d to xe2x80x9cWRITING DATAxe2x80x9d; means for changing the sector state information of the first sector from xe2x80x9cWRITING DATAxe2x80x9d to xe2x80x9cDATA WRITE COMPLETExe2x80x9d after the data writing for the first sector is completed; and means for a) when the data written to the first sector is new data, changing the sector state information of the first sector from xe2x80x9cDATA WRITE COMPLETExe2x80x9d to xe2x80x9cDATA VALIDxe2x80x9d, or b) when the data written to the sector is update data of existing data, changing the sector state information of a second sector from xe2x80x9cDATA VALIDxe2x80x9d to xe2x80x9cDATA INVALIDxe2x80x9d, and thereafter changing the sector state information of the first sector from xe2x80x9cDATA WRITE COMPLETExe2x80x9d to xe2x80x9cDATA VALIDxe2x80x9d.
In one embodiment of the invention, the file system control section includes: means for, during initialization of the file system performed when the power supply is restored, searching among the plurality of erasure blocks for an erasure block having the xe2x80x9cERASING ORIGINAL BLOCKxe2x80x9d block state information, and if an erasure block having the xe2x80x9cERASING ORIGINAL BLOCKxe2x80x9d block state information exists, locating a further erasure block from which data is to be transferred to the erasure block having the xe2x80x9cERASING ORIGINAL BLOCKxe2x80x9d block state information, based on the block state information in the file system memory section, means for erasing data in the further erasure block, and after completing the erasure, changing the block state information of the further erasure block from xe2x80x9cINCLUDES DATAxe2x80x9d to xe2x80x9cUNUSEDxe2x80x9d, means for changing the block state information of the erasure block having the xe2x80x9cERASING ORIGINAL BLOCKxe2x80x9d block state information from xe2x80x9cERASING ORIGINAL BLOCKxe2x80x9d to xe2x80x9cFORMATTING ORIGINAL BLOCKxe2x80x9d, formatting the erased further erasure block, and reserving the formatted erasure block as a new reserve erasure block; and means for changing the block state information of the erasure block having the xe2x80x9cFORMATTING ORIGINAL BLOCKxe2x80x9d block state information from xe2x80x9cFORMATTING ORIGINAL BLOCKxe2x80x9d to xe2x80x9cINCLUDES DATAxe2x80x9d after completing the formatting.
In another embodiment of the invention, the file system control section includes: means for, during initialization of the file system performed when the power supply is restored, searching among the plurality of erasure blocks for an erasure block having the xe2x80x9cFORMATTING ORIGINAL BLOCKxe2x80x9d block state information, and if an erasure block having the xe2x80x9cFORMATTING ORIGINAL BLOCKxe2x80x9d block state information exists, locating a further erasure block from which data is to be transferred to the erasure block having the xe2x80x9cFORMATTING ORIGINAL BLOCKxe2x80x9d block state information, based on the block state information in the file system memory section, means for formatting the further erasure block, and reserving the formatted erasure block as a new reserve erasure block; and means for changing the block state information of the erasure block having the xe2x80x9cFORMATTING ORIGINAL BLOCKxe2x80x9d block state information from xe2x80x9cFORMATTING ORIGINAL BLOCKxe2x80x9d to xe2x80x9cINCLUDES DATAxe2x80x9d after completing the formatting.
In another aspect of the invention, there is provided a method for managing a file system including at least one non-volatile semiconductor memory device, the at least one non-volatile semiconductor memory device including a plurality of erasure blocks, each erasure block including a plurality of sectors, wherein the file system includes: a file system memory section for storing block state information for each erasure block, the block state information representing one of a plurality of block states, and for storing sector state information for each sector, the sector state information representing one of a plurality of sector states; and a file system control section for, when accessing the at least one non-volatile semiconductor memory device, guaranteeing integrity of data already stored in the at least one non-volatile semiconductor memory device based on the block state information and on the sector state information in the file system memory section.
Alternatively, there is provided a method for managing a file system including at least one non-volatile semiconductor memory device, the at least one non-volatile semiconductor memory device including a plurality of sectors, wherein the file system includes: a file system memory section for storing sector state information for each sector, the sector state information representing one of a plurality of sector states; a file system control section for, when accessing the at least one non-volatile semiconductor memory device, guaranteeing integrity of data already stored, in the at least one non-volatile semiconductor memory device based on the sector state information in the file system memory section, wherein the plurality of sector states represented by the sector state information include the five states of xe2x80x9cUNUSEDxe2x80x9d, xe2x80x9cWRITING DATAxe2x80x9d, xe2x80x9cDATA WRITE COMPLETExe2x80x9d, xe2x80x9cDATA VALIDxe2x80x9d, and xe2x80x9cDATA INVALIDxe2x80x9d, and wherein the method includes: a step of changing the sector state information of a first sector in which data is written from xe2x80x9cUNUSEDxe2x80x9d to xe2x80x9cWRITING DATAxe2x80x9d; a step of changing the sector state information of the first sector from xe2x80x9cWRITING DATAxe2x80x9d to xe2x80x9cDATA WRITE COMPLETExe2x80x9d after the data writing for the first sector is completed; and a step of a) when the data written to the first sector is new data, changing the sector state information of the first sector from xe2x80x9cDATA WRITE COMPLETExe2x80x9d to xe2x80x9cDATA VALIDxe2x80x9d, or b) when the data written to the sector is update data of existing data, changing the sector state information of a second sector from xe2x80x9cDATA VALIDxe2x80x9d to xe2x80x9cDATA INVALIDxe2x80x9d, and thereafter changing the sector state information of the first sector from xe2x80x9cDATA WRITE COMPLETExe2x80x9d to xe2x80x9cDATA VALIDxe2x80x9d.
Alternatively, there is provided a method for managing a file system including at least one non-volatile semiconductor memory device, the at least one non-volatile semiconductor memory device including a plurality of sectors, wherein the file system includes: a file system memory section for storing sector state information for each sector, the sector state information representing one of a plurality of sector states; a file system control section for, when accessing the at least one non-volatile, semiconductor memory device, guaranteeing integrity of data already stored in the at least one non-volatile semiconductor memory device based on the sector state information in the file system memory section, wherein the plurality of sector states represented by the sector state information include the five states of xe2x80x9cUNUSEDxe2x80x9d, xe2x80x9cWRITING DATAxe2x80x9d, xe2x80x9cDATA WRITE COMPLETExe2x80x9d, xe2x80x9cDATA VALIDxe2x80x9d, and xe2x80x9cDATA INVALIDxe2x80x9d. and wherein the method includes: a step of changing the sector state information of a first sector in which data is written from xe2x80x9cUNUSEDxe2x80x9d to xe2x80x9cWRITING DATAxe2x80x9d; a step of changing the sector state information of the:first sector from xe2x80x9cWRITING DATAxe2x80x9d to xe2x80x9cDATA WRITE COMPLETExe2x80x9d after the data writing for the first sector is completed; and a step of a) when the data written to the first sector is new data, changing the sector state information of the first sector from xe2x80x9cDATA WRITE COMPLETExe2x80x9d to xe2x80x9cDATA VALIDxe2x80x9d, or b) when the data written to the sector is update data of existing data, changing the sector state information of a second sector from xe2x80x9cDATA VALIDxe2x80x9d to xe2x80x9cDATA INVALIDxe2x80x9d, and thereafter changing the sector state information of the first sector from xe2x80x9cDATA WRITE COMPLETExe2x80x9d to xe2x80x9cDATA VALIDxe2x80x9d.
Thus, the invention described herein makes possible the advantage of providing a file system incorporating a non-volatile semiconductor memory device which is capable of properly reading data that is stored in the non-volatile semiconductor memory device even if an interruption of the power supply occurs.
This and other advantages of the present invention will become apparent to those skilled in the art upon reading and understanding the following detailed description with reference to the accompanying figures.